\section{集合}
\subsection{集合的基本概念}
\subsubsection{集合的基本性质}
集合是可辨认的个体的汇集
\begin{enum}
    \item 定义任意性：可以取任意多个不同种类的元素来组成一个集合
    \item 元素确定性：$a\in A$ 与 $a\not \in A$ 有且仅有一个为真
    \item 元素无序性：各个元素地位相同
    \item 元素互异性：每个元素最多出现一次
\end{enum}

特殊的集合：空集 $\varnothing$，全集 $X$

\subsubsection{集合的关系}
\emph{子集}：$\forall a\in A, a\in B \iff A\subseteq B$\\
\emph{相等}：$A\subseteq B \land B\subseteq A \iff A=B$

$\forall A$,
\begin{enum}
    \item $A\subseteq X$，任意集合是全集的子集
    \item $\varnothing \subseteq A$，空集是任意集合的子集
    \item $A \subseteq A$，任意集合是本身的子集
\end{enum}

\subsubsection{幂集}
\emph{幂集}：集合 $A$ 的所有子集构成的集合称为 $A$ 的幂集，记为 $2^{A}$
$$
2^A = \{x \,|\, x\subseteq A\}
$$

\begin{enum}
    \item 空集的幂集不是空集 $2^{\varnothing} = \{\varnothing\} \neq \varnothing$
    \item $A=B \iff 2^A = 2^B$
\end{enum}

\begin{quote}
    证明 $A=B\iff 2^A=2^B$：

    先证 $A=B \Longrightarrow 2^A=2^B$
    $$
    \left.\begin{aligned}
        \forall x\in 2^A, x\subseteq A\\
        A=B
    \end{aligned}\right\}
    \qquad\Longrightarrow\qquad x\subseteq B \iff x\in 2^B
    \qquad\Longrightarrow\qquad 2^A\subseteq 2^B
    $$
    同理可得$2^B \subseteq 2^A$，因此 $2^A=2^B$
    
    再证 $2^A = 2^B \Longrightarrow A=B$
    $$
    \left.\begin{aligned}
        \forall x\in A, \{x\} \in 2^A\\
        2^A=2^B
    \end{aligned}\right\}
    \qquad\Longrightarrow\qquad \{x\}\in 2^B \iff \{x\}\subseteq B \;\Longrightarrow x\in B
    \qquad\Longrightarrow\qquad A\subseteq B
    $$
    同理可得 $B\subseteq A$，因此 $A=B$
\end{quote}

\subsubsection{基数}
\emph{基数}：当 $A$ 的元素只有有穷个时，称集合中元素的个数为 $A$ 的基数 $|A|$

\begin{enum}
    \item $\left|2^A\right|=2^{|A|}$
\end{enum}

\begin{quote}
    证明 $\left|2^A\right| = 2^{|A|}$：\\
    设 $n=|A|$，则 $|2^A| = \mathrm C_{n}^0 + \mathrm C_{n}^1 + \cdots + \mathrm C_{n}^{n} = 2^{n}=2^{|A|}$
\end{quote}

\subsection{集合的基本运算}
\subsubsection{补集}
$A$ 关于全集 $X$ 的\emph{补集}：$A' = \{x \,|\, x\in X \land x\not\in A\}$

\begin{enum}
    \item $x\not\in A \iff x\in A'$
    \item $x\not\in A' \iff x\in A$
    \item $(A')'=A$
    \item $A\subseteq B \iff B'\subseteq A'$
    \item $A=B \iff A'=B'$
    \item $X'=\varnothing$
    \item $\varnothing'=X$
\end{enum}

\begin{quote}
    证明：$A\subseteq B \iff B'\subseteq A'$
    $$
    \left.\begin{aligned}
        \forall x\in B', x\not\in B\\
        A\subseteq B
    \end{aligned}\right\}
    \qquad\Longrightarrow\qquad 
    x\not \in A \iff x\in A'
    \qquad\Longrightarrow\qquad 
    B' \subseteq A'
    $$
\end{quote}

\begin{quote}
    $X' = \{x\,|\, x\in X \land x \not\in X\} = \varnothing$\\
    $\varnothing' = \{x \,|\, x\in X \land x\not\in \varnothing\} = \{x\,|\, x\in X\} = X$
\end{quote}

\subsubsection{交集与并集}
\emph{交集} $A\cap B = \{ x\,|\, x\in A \land x\in B\}$\\
\emph{并集} $A\cup B = \{ x\,|\, x\in A \lor  x\in B\}$\\
交集、并集相关定理如表 \ref{tab:交集、并集的相关定理} 所示

\begin{table}[htpb]
    \centering
    \caption{交集、并集的相关定理}
    \label{tab:交集、并集的相关定理}
    \begin{tabular}{ll|c}
        \toprule
        $A\cap A=A$ & $A\cup A=A$ & {\kaishu 幂等律} \\
        $A\cap A'=\varnothing$ & $A\cup A'=X$ & {\kaishu 互补律}\\
        \hline
        $A\cap X=A$ & $A\cup X=X$ & \multirow{2}{*}{\kaishu 零一律} \\
        $A\cap \varnothing=\varnothing$ & $A\cup \varnothing=A$ & \\
        \hline
        $A\subseteq (A\cup B)$ & $(A\cap B)\subseteq A$ & {\kaishu 上下界} \\
        \multicolumn{2}{l|}{$A\subseteq C \land B\subseteq C \qquad\quad\;\Longrightarrow\qquad\quad\,\;
            (A\cup B)\subseteq C$} & {\kaishu 上确界} \\
        \multicolumn{2}{l|}{$C\subseteq A \land C\subseteq B \qquad\quad\;\Longrightarrow\qquad\quad\,\;
            C\subseteq (A\cap B)$} & {\kaishu 下确界} \\
        \hline
        $A \cap (A\cup B) = A$ & $A\cup (A\cap B)=A$ & {\kaishu 吸收律}\\
        \hline
        $A \cap B = B\cap A$ & $A \cup B = B\cup A$  & {\kaishu 交换律}\\
        $A \cap (B\cap C) = (A\cap B)\cap C$ & $A \cup (B\cup C) = (A\cup B)\cup C$ & {\kaishu 结合律}\\
        $A\cap(B\cup C) = (A\cap B) \cup (A\cap C)$ & $A\cup(B\cap C) = (A\cup B) \cap (A\cup C)$ & {\kaishu 分配律} \\
        \hline 
        $(A\cap B)' = A' \cup B'$ & $(A\cup B)' = A' \cap B'$ & {\kaishu 摩根律}\\
        \hline
        \multicolumn{2}{l|}{$A \subseteq B \iff A\cap B = A \iff A\cup B = B$} & \\
        \bottomrule
    \end{tabular}
\end{table}

\paragraph{证明分配律}
证明 $(A\cap B) \cup (A\cap C) = A\cap (B\cup C)$：\\
先证 $(A\cap B) \cup (A\cap C) \subseteq A\cap (B\cup C)$
$$
\left.\begin{aligned}
\left.\begin{aligned}
    (A\cap B) \subseteq A\\
    (A\cap B)\subseteq B\subseteq (B\cup C)
\end{aligned}\right\} 
\;\;\Longrightarrow\;\;
(A\cap B) \subseteq \big(A\cap (B\cup C)\big)\\
\text{Similarly, }
(A\cap C) \subseteq \big(A\cap (B\cup C)\big)
\end{aligned}\right\}
\;\;\Longrightarrow\;\;
(A\cap B) \cup (A\cap C) \subseteq A\cap (B\cup C)
$$
再证$A\cap(B\cup C)\subseteq \big((A\cap B) \cup (A\cap C)\big)$，用元素法易证

证明 $(A\cup B) \cap (A\cup C) = A\cup (B\cap C)$：\\
先证$A\cup(B\cap C)\subseteq \big((A\cup B) \cap (A\cup C)\big)$
$$
\left.\begin{aligned}
\left.\begin{aligned}
    A \subseteq (A\cup B)\\
    A \subseteq (A\cup C)\\
\end{aligned}\right\} 
\!\Longrightarrow\;\;
A\subseteq \big((A\cup B) \cap (A\cup C)\big)\\
\left.\begin{aligned}
    (B\cap C) \subseteq B \subseteq (A\cup B)\\
    (B\cap C) \subseteq C \subseteq (A\cup C)
\end{aligned}\right\}
\!\Longrightarrow\;\;
(B\cap C)\subseteq \big((A\cup B) \cap (A\cup C)\big)
\end{aligned}\right\}
\!\Longrightarrow\;\;
A\cup(B\cap C)\subseteq \big((A\cup B) \cap (A\cup C)\big)
$$

再证 $\big((A\cup B) \cap (A\cup C)\big)\subseteq A\cup(B\cap C)$，用元素法易证



\subsection{集合的宏运算}
可以用集合的并、交、补表示的运算称为集合的宏运算
\subsubsection{集合的差运算}
\emph{差集} $A\backslash B=\{x\,|\, x\in A \land x\not\in B\}=A\cap B'$
\begin{enum}
    \item $A\backslash B \subseteq A$
    \item $A\subseteq B \;\;\Longrightarrow\;\; A\backslash B = \varnothing$
    \item $X\backslash A = A'$，$A\backslash \varnothing = A$
    \item $A\cap (B\backslash C) = (A\cap B) \backslash (A\cap C)$
    \item $A\backslash (B\backslash C) = (A\backslash B) \cup (A\cap C)$
    \item $A\backslash (B\cap C) = (A\backslash B) \cup (A\backslash C)$
    \item $A\backslash (B\cup C) = (A\backslash B) \cap (A\backslash C)$
\end{enum}

\subsubsection{集合的对称差运算}
\emph{环和} $A\oplus B = (A\backslash B) \cup (B\backslash A) = (A\cap B')\cup (B\cap A')$
\begin{enum}
    \item $A\oplus B = (A\cup B) \backslash (A\cap B)$
    \item $A\oplus \varnothing = A$，$A\oplus X = A'$
    \item $A\oplus A = \varnothing$，$A\oplus A' = X$
    \item $A\oplus B = A' \oplus B'$
    \item $A' \oplus B = A\oplus B' = (A\oplus B)' = A\otimes B$
    \item $A\oplus B = B\oplus A$
    \item $A\oplus (B\oplus C) = (A\oplus B) \oplus C$
    \item $A\cap (B\oplus C) = (A\cap B) \oplus (A\cap C)$
    \item $A\oplus B = A\oplus C \iff B=C$
\end{enum}

\subsubsection{集合的环积运算}
\emph{环积} $A\otimes B = (A\oplus B)'$

\subsection{大交与大并}
大交 $\bigcap_{\gamma\in\Gamma}A_{\gamma} = \{ x\,|\, (\forall\gamma\in\Gamma)(x\in A_{\gamma})\}$\\
大并 $\bigcup_{\gamma\in\Gamma}A_{\gamma} = \{ x\,|\, (\exists\gamma\in\Gamma)(x\in A_{\gamma})\}$
\begin{align*}
&A \cup\left(\bigcup_{\gamma \in \Gamma} A_{\gamma}\right)=\bigcup_{\gamma \in \Gamma}\left(A \cup A_{\gamma}\right) & 
&A \cup\left(\bigcap_{\gamma \in \Gamma} A_{\gamma}\right)=\bigcap_{\gamma \in \Gamma}\left(A \cup A_{\gamma}\right) \\
&A \cap\left(\bigcap_{\gamma \in \Gamma} A_{\gamma}\right)=\bigcap_{\gamma \in \Gamma}\left(A \cap A_{\gamma}\right) & 
&A \cap\left(\bigcup_{\gamma \in \Gamma} A_{\gamma}\right)=\bigcup_{\gamma \in \Gamma}\left(A \cap A_{\gamma}\right) \\
&\left(\bigcup_{\gamma \in \Gamma} A_{\gamma}\right)^{\prime}=\bigcap_{\gamma \in \Gamma}\left(A_{\gamma}^{\prime}\right) &
&\left(\bigcap_{\gamma \in \Gamma} A_{\gamma}\right)^{\prime}=\bigcup_{\gamma \in \Gamma}\left(A_{\gamma}^{\prime}\right) 
\end{align*}

\subsection{集合的其它表示法}
\subsubsection{成员表法}
举例：证明 $B\cup C \subseteq (A\cap B)\cup (C\backslash A)$
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/成员表法举例.png}
    \caption{成员表法举例}
    \label{fig:成员表法举例}
\end{figure}

\section{关系}

\subsection{集合的叉积}

\emph{二元组}  $(a,b)$，\emph{$m$元组} $(a_1,a_2,\cdots,a_m)$
\begin{enum}
    \item 计较顺序
    \item 同维度的元组，若对应位置上的分量分别相等，定义它们相等
\end{enum}

\emph{叉积}：$A\times B = \{(a,b)\,|\, a\in A \land b\in B\}$，其中 $A,B\ne \varnothing$
\begin{enum}
    \item $A$ 称为\emph{前集}，$B$ 称为\emph{后集}
    \item 若 $A=B$ 则记 $A\times B = A^2$
    \item 定义 $A\times \varnothing = \varnothing \times B = \varnothing$
\end{enum}


叉积的运算性质：
\begin{enum}
    \item $A\times B = C \times D \iff A=C \land B=D$
    \item 对交/并的左/右分配律\\
            $
            \begin{aligned}
            &A \times(B \cup C)=(A \times B) \cup(A \times C) \\
            &A \times(B \cap C)=(A \times B) \cap(A \times C) \\
            &(A \cup B) \times C=(A \times C) \cup(B \times C) \\
            &(A \cap B) \times C=(A \times C) \cap(B \times C)
            \end{aligned}
            $
\end{enum}

\subsection{关系}
\subsubsection{关系的基本概念}
\emph{关系}：若 $R\subseteq A\times B$ 则称 $R$ 是 $A,B$ 的元素之间的一个二元关系
\begin{enum}
    \item $a\in A \land b\in B \land (a,b)\in R$ 则称 $a$ 与 $b$ 有关系 $R$
    \item \emph{全关系}：$R=A\times B$
    \item \emph{空关系}：$R=\varnothing$
    \item \emph{幺关系}：$R=\{(a,a)\,|\,a\in A\}\subseteq A\times A$ 称为 $A$ 上的幺关系
\end{enum}

\emph{$n$ 元关系}：若 $R\in A_1 \times A_2 \times \cdots \times A_n$

\subsubsection{关系的前域后域}
\emph{前域}：$\mathscr D(R) = \{a \,|\, a\in A \land (\exists b\in B)(a,b)\in R\}\subseteq A$\\
\emph{后域}：$\mathscr R(R) = \{b \,|\, b\in B \land (\exists a\in A)(a,b)\in R\}\subseteq B$
\begin{enum}
    \item $R_1 \subseteq R_2 \subseteq A\times B \;\;\Longrightarrow\;\; \mathscr D(R_1)\subseteq \mathscr D(R_2)$\\
          $R_1 \subseteq R_2 \subseteq A\times B \;\;\Longrightarrow\;\; \mathscr R(R_1)\subseteq \mathscr R(R_2)$
    \item $\mathscr{D}\left(R_{1} \cup R_{2}\right)=\mathscr{D}\left(R_{1}\right) \cup \mathscr{D}\left(R_{2}\right)$\\
          $\mathscr{R}\left(R_{1} \cup R_{2}\right)=\mathscr{R}\left(R_{1}\right) \cup \mathscr{R}\left(R_{2}\right)$ \\
          $\mathscr{D}\left(R_{1} \cap R_{2}\right) \subseteq \mathscr{D}\left(R_{1}\right) \cap \mathscr{D}\left(R_{2}\right)$ \\
          $\mathscr{R}\left(R_{1} \cap R_{2}\right) \subseteq \mathscr{R}\left(R_{1}\right) \cap \mathscr{R}\left(R_{2}\right)$
\end{enum}

\subsubsection{关系的表示法}
\paragraph{关系矩阵}
设 $R\subseteq A\times B$ 且 $|A|=m,|B|=n$，则可用 $m\times n$ 矩阵 $M_{R}$来表示 $R$，称 $M_R$ 为关系 $R$ 的\emph{关系矩阵}
$$
(M_R)_{ij} = \left\{
\begin{aligned}
    &1, &(a_i,b_j)\in R\\
    &0, &(a_i,b_j)\not\in R
\end{aligned}\right.
$$

若前集、后集是相同集合，则关系矩阵是方阵

\paragraph{关系的图形表示法}
将$A$ 中元素 $a_1,a_2,\cdots,a_m$ 和 $B$ 中元素$b_1,b_2,\cdots b_n$ 作为图上的结点，分别置于两侧\\
若 $(a_i,b_j)\in R$ 则将 $a_i$ 通过有向弧指向 $b_j$\\
各有向弧的始端构成 $\mathscr D(R)$，终端构成 $\mathscr R(R)$

\subsection{关系的运算}
\subsubsection{逆关系}
$A\ne \varnothing,\;\forall R\subseteq A\times B$\\
\emph{逆关系}：$\widetilde{R} = \{(b,a)\,|\, b\in B \land a\in A \land (a,b)\in R\}\subseteq B\times A$
\begin{enum}
    \item $(b,a)\in \widetilde{R} \iff (a,b) \in R$
    \item $\doublewidetilde{R} = R$
    \item $R \subseteq S \;\; \Longrightarrow \;\; \widetilde R \subseteq \widetilde S$ 
    \item $R = S \;\; \Longrightarrow \;\; \widetilde R =\widetilde S$ 
    \item $\widetilde{R\cap S} = \widetilde{R} \cap \widetilde{S}$
    \item $\widetilde{R\cup S} = \widetilde{R} \cup \widetilde{S}$
    \item $\widetilde{R\backslash S} = \widetilde{R} \backslash \widetilde{S}$
    \item $\widetilde{(R)'} = \big(\widetilde{R}\,\big)'$
    \item $\widetilde{X\times Y} = Y\times X$
    \item $M_{\widetilde{R}} = (M_{R})^{\rm T}$
\end{enum}

\subsubsection{关系的复合}
$\forall R\subseteq A\times B,\; S\subseteq B\times C$\\
\emph{复合关系} $R\circ S = \big\{(a,c)\,|\, a\in A \land c\in C \land 
\big(\exists b\in B\big)\big((a,b)\in R\land (b,c)\in S\big)\big\}\subseteq A\times C$\\
称$B$为\emph{媒介集合}，$B$ 同时是 $R$ 的后集与 $S$ 的前集
\begin{enum}
    \item $R\circ \varnothing = \varnothing \circ S = \varnothing$
    \item $\mathscr D(R\circ S) \subseteq \mathscr D(R), \,\mathscr R(R\circ S) \subseteq \mathscr R (S)$
    \item 保序性：$R_1\subseteq R, S_1\subseteq S \;\;\Longrightarrow\;\; R_1\circ S_1 \subseteq R\circ S$
    \item 交换律：$R\circ(S\circ T) = (R\circ S)\circ T$
    \item 对并运算的分配律\\
          $R \circ\left(S_{1} \cup S_{2}\right)=\left(R \circ S_{1}\right) \cup\left(R \circ S_{2}\right) $\\
          $\left(S_{1} \cup S_{2}\right) \circ T=\left(S_{1} \circ T\right) \cup\left(S_{2} \circ T\right) $
    \item 对交运算的分配律\\ 
          $R \circ\left(S_{1} \cap S_{2}\right) \subseteq\left(R \circ S_{1}\right) \cap\left(R \circ S_{2}\right) $\\
          $\left(S_{1} \cap S_{2}\right) \circ T \subseteq\left(S_{1} \circ T\right) \cap\left(S_{2} \circ T\right) $
    \item $\widetilde{R \circ S}=\widetilde{S} \circ \widetilde{R}$
\end{enum}

\subsubsection{关系运算的矩阵表示法}
补运算：关系矩阵逐项布尔取反\\
交运算：关系矩阵逐项布尔乘\\
并运算：关系矩阵逐项布尔加\\
逆关系：关系矩阵转置\\
复合关系：关系矩阵进行矩阵乘法（布尔乘、布尔加）

\subsection{二元关系的基本性质}
\subsubsection{自反/反自反}
$A\ne\varnothing$，$R\subseteq A\times A$，$\forall x\in A$\\
$(x,x)\in R$ 则称 $R$ 是 $A$ 上的\emph{自反关系}\\
$(x,x)\not\in R$ 则称 $R$ 是 $A$ 上的\emph{反自反关系}

自反关系的关系矩阵对角线元素必须全为1，关系图的每个结点都有自反圈\\
反自反关系关系矩阵对角线元素必须全为0，关系图的每个结点都无自反圈

\subsubsection{对称/反对称}
$A\ne\varnothing$，$R\subseteq A\times A$\\
若 $\forall (x,y)\in R,\, (y,x)\in R$ 则称 $R$ 是 $A$ 上的\emph{对称关系}\\
若 $(x,y)\in R \land (y,x)\in R $ 可推出 $x=y$ 则称 $R$ 是 $A$ 上的\emph{反对称关系}

对称关系的关系矩阵是对称矩阵\\
反对称关系关系矩阵若某处为1则对称处必为0

对称关系的关系图若结点间有弧则必须是双向弧\\
反对称关系关系图若结点间有弧则必须是单项弧

\begin{quote}
    对称与反对称可以共存，例如幺关系既是对称关系，又是反对称关系
\end{quote}

\subsubsection{传递性}
$A\ne\varnothing$，$R\subseteq A\times A$，$\forall x,y,z\in A$\\
若当 $(x,y)\in R, (y,z)\in R$ 时有 $(x,z)\in R$，则称 $R$ 是 $X$ 上的\emph{传递关系}

\subsection{关系的复合幂与闭包}
\subsubsection{关系的复合幂}
\emph{复合幂}：$A\ne \varnothing$，$R\subseteq A\times A$，$n\in \mathbb N^+$，规定：
\begin{enum}
    \item $R^0 = I$
    \item $R^1 = R$
    \item $R^{n+1} = R^n \circ R$
\end{enum}

复合幂的运算律（用数学归纳法证明）
\begin{enum}
\item $R^m \circ R^n = R^n \circ R^m = R^{n+m}$
\item $(R^n)^m = (R^m)^n = R^{mn}$
\end{enum}

\begin{quote}
$(a,b)\in R\cup R^2 \cup R^3$ 则称 $a$ 与 $b$ 有直接的 $R$ 关系，或间接 $R$ 关系，或二阶间接 $R$ 关系
\end{quote}

\subsubsection{关系的包}

$A\ne\varnothing$，$R\subseteq A\times A$，$S\subseteq A\times A$\\
\emph{包}：令 $R^+ = \bigcup_{k=1}^{+\infty} R^k$，称 $R^+$ 为关系 $R$ 的包
\begin{enum}
    \item $\forall m\in \mathbb N^+,\, R^m\subseteq R^+$
    \item $R^+$ 是传递关系
    \item $R\subseteq S$ 且 $S$ 是传递关系，则 $R^+\subseteq S$（即$R^+$是包含 $R$ 的最小传递关系）
    \item 若 $|A|=n$ 则 $R^+=\bigcup_{k=1}^n R^k$
\end{enum}

证明 $R^+$ 是传递关系\\
若 $(a,b)\in R^+$ 且 $(b,c)\in R^+$ 则 $\exists k,l\in\mathbb N$ 使 $(a,b)\in R^k$ 且 $(b,c)\in R^l$\\
则 $(a,c)\in R^k\circ R^l = R^{k+l} \subseteq R^+$ 也就是 $(a,c)\in R^+$

证明 $R^+$ 是包含 $R$ 的最小传递关系\\
若 $(a,b)\in R^+$ 则 $\exists k\in \mathbb N,\, (a,b)\in R^k$，则存在 $(a,t_1)\in R,\,(t_1,t_2)\in R,\,\cdots\, ,(t_{k-1},b)\in R$\\
由$R\subseteq S$ 得 $(a,t_1)\in S,\,(t_1,t_2)\in S,\,\cdots\, ,(t_{k-1},b)\in S$\\
由$S$ 为传递关系得 $(a,b)\in S$，因此 $R^+\subseteq S$

证明 $R^+ = \bigcup_{k=1}^{|A|} R^k$\\
若 $(a,b)\in R^+$，则存在 $m\in\mathbb N^+$ 使 $(a,b)\in R^m$\\
假定满足上式的最小 $m$ 为 $m_0$，因此存在 $(a,t_1),\cdots,(t_{m_0-1},b)\in R$\\
这给出了 $A$ 中的 $m_0+1$ 个元素 $a,t_1,\cdots,t_{m_0-1},b$\\
若 $m_0>|A|$ 则不可能使 $t_1,\cdots,t_{m_0-1}$ 互不相等，则 $m_0$ 可以进一步缩小\\
这与假设矛盾，故 $m_0\le |A|$


\subsubsection{关系的星包}
\emph{星包}：$R\subseteq A\times A$ 且 $R\ne \varnothing$， 令 $R^* = R^+ \cup I = \bigcup _{k=0}^{+\infty}R^k$，
称 $R^*$ 为关系 $R$ 的星包
\begin{enum}
    \item $\forall m\in \mathbb N,\, R^m\subseteq R^+$
    \item $R^*$ 是自反的传递关系
    \item $R\subseteq S$ 且 $S$ 是自反的传递关系，则 $R^*\subseteq S$（即$R^*$是包含 $R$ 的最小自反传递关系）
    \item 若 $|A|=n$ 则 $R^*=\bigcup_{k=0}^n R^k$
\end{enum}


\subsection{等价关系}
\subsubsection{等价关系与等价类}
$A\ne \varnothing,\;R\subseteq A\times A$\\
若 $R$ 是自反、对称、传递的，则称 $R$ 是 $A$ 上的\emph{等价关系}

设 $R$ 是非空集合 $A$ 上的等价关系，$\forall a\in A$ 称集合 $\{b\,|\,(b,a)\in R\}$ 为 $a$ 关于 $R$ 的\emph{等价类}，记为 $[a]_R$\\
称 $a$ 为为等价类 $[a]_{R}$  的代表元素
\begin{enum}
\item 每个元素都属于某一个等价类：$\forall a\in A, a\in[a]_R \ne \varnothing$
\item $(a,b)\in R \iff [a]_R = [b]_R$
\item 一个元素只能属于一个等价类：若$[a]_R\cap [b]_R\ne \varnothing$ 则 $[a]_R = [b]_R$
\item $\bigcup_{a\in A} [a]_R = A$
\item $R_1\subseteq R_2 \iff \forall a\in A, [a]_{R_1}\subseteq [a]_{R_2}$，此时称$R_1$ \emph{细于} $R_2$
\item $R_1 = R_2 \iff \forall a\in A, [a]_{R_1} = [a]_{R_2}$，等价关系与等价类集合一一对应
\end{enum}

\begin{quote}
    等价类不重不漏地将 $A$ 中元素分组
\end{quote}


设 $R$ 是非空集合 $A$ 上的等价关系\\
$\Pi_R = \{[a]_{R}\,|\,a\in A\}$，称 $\Pi_R = A/R$ 为 $A$ 关于等价关系 $R$ 的\emph{商集}，称 $A/R$ 中元素的个数为 $R$ 的\emph{秩}
\begin{enum}
\item 若 $R$ 是全关系，则 $A/R = \{A\}$（分类最粗）
\item 若 $R$ 是幺关系，则 $A/R=\{\{a\}\,|\, a\in A\}$（分类最细）
\end{enum}

\subsubsection{划分与覆盖}

$A\ne \varnothing,\;\Pi = \{A_\gamma \,|\, \gamma\in \Gamma \land A_\gamma \ne \varnothing\}$
\begin{enum}
    \item 若 $A\subseteq \bigcup_{\gamma\in \Gamma} A_\gamma$ 则称 $\Pi$ 是 $A$ 上的\emph{覆盖}
    \item 若 $A = \bigcup_{\gamma\in \Gamma} A_\gamma$ 且当 $\gamma_1\ne\gamma_2$ 时有 $A_{\gamma_1} \cap A_{\gamma_2}=\varnothing$
则称 $\Pi$ 为 $A$ 的一个\emph{划分}
\end{enum}


$R$ 是非空集合 $A$ 上的等价关系，则 $\Pi_R = \{[a]_R\,|\,a\in A\}$ 是 $A$ 上的一个划分 \\
$\Pi$ 是非空集合 $A$ 上的一个划分，则由 $\Pi$ 可产生 $A$ 上的一个等价关系$R_\Pi$
$$
R_\Pi=\{(x,y)\,|\,x\in A\land y\in A \land (\exists \gamma\in \Gamma)(x\in A_\gamma\land y\in A_\gamma)\}
$$

\begin{quote}
    $A$ 关于等价关系 $R$ 的等价类集合就是 $A$ 的一个划分
\end{quote}

若 $R$ 是非空集合 $A$ 上的等价关系，$\Pi=\{[x]_R\,|\, x\in A\}$，由 $\Pi$ 产生出等价关系 $R_1$，则 $R=R_1$\\
若 $\Pi$ 是非空集合 $A$ 上的一个划分，由 $\Pi$ 产生出等价关系 $R$，由 $R$ 产生出划分 $\Pi_1$，则 $\Pi=\Pi_1$

\begin{quote}
划分与等价关系是一一对应的
$$
\begin{aligned}
    R &= \{(x,y)\,|\,x\in A\land y\in A \land (\exists \gamma\in \Gamma)(x\in A_\gamma\land y\in A_\gamma)\}\\
    \Pi &= \{[a]_R\,|\,a\in A\}
\end{aligned}
$$
\end{quote}

\subsubsection{相容关系}
设 $R$ 是非空集合 $A$ 上的二元关系，若 $R$ 是自反、对称的，则称 $R$ 是 $A$ 上的\emph{相容关系}\\
相容关系产生的结构是覆盖

\subsection{半序关系}
$R$ 是非空集合 $A$ 上的二元关系\\
若 $R$ 是自反、反对称、传递的，则称 $R$ 是 $A$ 上的\emph{半序关系}
\begin{enum}
\item 元素间存在一定的可比性：某些元素之间可比较，另一些元素之间不可比较
\item 依赖可比性将 $A$ 中元素进行一定的分层
\end{enum}

常用 \emph{Hasse 图}来表示半序关系，其在关系图上进行如下改动
\begin{enum}
    \item 由自反性，每个元素都有自环，在Hasse图中省略自环
    \item 由反对称性，只有单向弧。在Hasse图中规定弧线一律由下指向上，省略箭头
    \item 由传递性，在Hasse图中可通过现有弧线传递得到的弧线省略不画
\end{enum}

\subsubsection{半序集中的特殊元素}
设 $(A,\preccurlyeq)$ 为半序集，$B\subseteq A$
\begin{enum}
\item \makebox[2.4cm][l]{若存在$x_0\in A$}\makebox[3.35cm][l]{使$({\color{blue}\forall } a\in A)(a\preccurlyeq x_0)$ }\makebox[1.2cm][l]{则称 $x_0$}\makebox[5cm][l]{ 是 $A$ 上的\emph{最大元}}
\item \makebox[2.4cm][l]{若存在$y_0\in A$}\makebox[3.35cm][l]{使$({\color{blue}\forall } a\in A)(y_0\preccurlyeq a)$ }\makebox[1.2cm][l]{则称 $y_0$}\makebox[5cm][l]{ 是 $A$ 上的\emph{最小元}}
\item \makebox[2.4cm][l]{任取一$x_0\in A$}\makebox[3.35cm][l]{若$({\color{blue}\nexists} a\in A)(x_0\preccurlyeq a)$ }\makebox[1.2cm][l]{则称 $x_0$}\makebox[5cm][l]{ 是 $A$ 上的\emph{极大元}}
\item \makebox[2.4cm][l]{任取一$y_0\in A$}\makebox[3.35cm][l]{若$({\color{blue}\nexists} a\in A)(a\preccurlyeq y_0)$ }\makebox[1.2cm][l]{则称 $y_0$}\makebox[5cm][l]{ 是 $A$ 上的\emph{极小元}}
\item \makebox[2.4cm][l]{若存在$x_0\in A$}\makebox[3.35cm][l]{使$({\color{blue}\forall } b\in B)(b\preccurlyeq x_0)$ }\makebox[1.2cm][l]{则称 $x_0$}\makebox[5cm][l]{ 是 $B$ 的一个\emph{上界}}
\item \makebox[2.4cm][l]{若存在$y_0\in A$}\makebox[3.35cm][l]{使$({\color{blue}\forall } b\in B)(y_0\preccurlyeq b)$ }\makebox[1.2cm][l]{则称 $y_0$}\makebox[5cm][l]{ 是 $B$ 的一个\emph{下界}}
\item $x_0$ 是 $B$ 的上界，对任意 $B$ 的上界 $x$ 都有 $x_0\preccurlyeq x$ 则称 $x_0$ 是 $B$ 的\emph{上确界}，
      记为 $\operatorname{LUB}(B)$
\item $y_0$ 是 $B$ 的下界，对任意 $B$ 的下界 $y$ 都有 $y\preccurlyeq y_0$ 则称 $y_0$ 是 $B$ 的\emph{下确界}，
      记为 $\operatorname{GLB}(B)$
\end{enum}

\begin{quote}
    $\forall$ 要求所有的$a,b$ 均与 $x_0,y_0$ 可比，元素不一定有资格参与鉴定，故最前方用“若存在”\\
    $\nexists$ 允许与 $x_0,y_0$不可比的元素存在，所有元素均有资格参与鉴定，故最前方用“任取”
\end{quote}

相关定理
\begin{enum}
    \item 非空有限半序集上必定存在极大元与极小元，但不一定唯一\\
          在无穷半序集中不一定存在极大元或极小元
    \item 若存在最大元/最小元，则有且只有一个最大元/最小元\\
        证明：假设有两个最大元 $x_1,x_2$ 则 $(x_1\preccurlyeq x_2)\land(x_2\preccurlyeq x_1)$，则由反对称性 $x_1=x_2$
    \item 若存在极大元/极小元且唯一，则它也是最大元/最小元
    \item $B$ 的上下确界不一定在 $B$ 中
    \item $B$ 的有上界不一定有上确界，若有上确界则必定唯一
\end{enum}

%\begin{quote}
%    若存在 $a$ 与 $x$ 不可比，则 $x$ 一定不为最大元/最小元、上界/下界、上确界/下确界\\
%    但 $x$ 可能是极大元/极小元
%\end{quote}

\subsection{全序关系}
$(A,\preccurlyeq)$ 是半序集\\
若 $\forall a,b\in A$ 有 $a\preccurlyeq b \lor b\preccurlyeq a$ 则称 $(A,\preccurlyeq)$ 为\emph{全序集}，$\preccurlyeq$ 为全序关系

$(A,\preccurlyeq)$ 是全序集\\
任取 $a,b\in A$ 且 $(a\le b) \land (a\ne b)$，$\forall(t\in A) \land (a\le t \le b)$ 有 $(t=a)\lor(t=b)$，
则称$b$ 是 $a$ 的\emph{直接后继}

$(A,\preccurlyeq)$ 是半序集\\
若 $A$ 的每个非空子集都有最小元素，则称 $(A,\preccurlyeq)$ 为\emph{良序集}，称$\preccurlyeq$ 为\emph{良序关系}
\begin{enum}
    \item $\preccurlyeq$ 是全序关系
    \item $\forall a\in A$，若 $a$ 不是 $A$ 的最大元，则存在 $a$ 的直接后继 $a+1$
\end{enum}

\section{函数}
\subsection{函数的基本概念}
$X\ne \varnothing ,Y\ne \varnothing$，$f$ 是从 $X$ 到 $Y$ 的二元关系\\
若 $\forall x\in X$ 存在唯一 $y\in Y$ 使得 $(x,y)\in f$，则称$f$ 是从 $X$ 到 $Y$ 的\emph{函数}，记为 $f:X\to Y$
\begin{enum}
    \item 前域充满 $\mathscr D(f) = X$
    \item 后者唯一
\end{enum}

其它定义：
\begin{enum}
\item 从 $X$ 到 $Y$ 的所有函数的集合记为 $Y^X = \{f\,|\,f:X\to Y\}$
\item 若 $\mathscr R(f) = Y$ 则称 $f$ 是\emph{满射}的
\item 若当 $x_1\ne x_2$ 时有 $f(x_1)\ne f(x_2)$ 则称 $f$ 是\emph{单射}的
\item 若 $f$ 既是满射又是单射，则称 $f$ 是\emph{双射}的
\item 若 $f$ 是双射函数，则 $f^{-1} = \widetilde{f}$ 是从 $Y$ 到 $X$ 的双射函数，且$(f^{-1})^{-1}=f$
\end{enum}

\begin{quote}
    证明：$f^{-1}\circ f = I_X$
    $$
    I_X(x) = x = f^{-1}(y)= f^{-1}(f(x)) = (f^{-1}\circ f)(x)
    $$
\end{quote}

$A,B,C\ne \varnothing$，$f$ 是从 $X$ 到 $Y$ 的函数，$g$ 是从 $Y$ 到 $Z$ 的函数
\begin{enum}
\item 复合关系 $f\circ g$ 是 $X\to Z$ 的函数，记为 $g\circ f$
\item 定义 $f^1=f$，$f^{n+1} = f\circ f^{n}$，若 $f^2=f$ 则称$f$ 为\emph{幂等函数}
\item 若 $f$ 与 $g$ 都是满射函数，则 $g\circ f$ 是满射函数
\item 若 $f$ 与 $g$ 都是单射函数，则 $g\circ f$ 是单射函数
\item 若 $f$ 与 $g$ 都是双射函数，则 $g\circ f$ 是双射函数
\end{enum}

\subsection{集合的基数}

%\begin{quote}
%对有限多个元素的集合 $A$，其基数 $|A|$ 定义为 $A$ 包含的元素个数
%\end{quote}

对两个集合 $A,B$，若存在双射函数 $f:A\to B$，则称 $A$ 与 $B$ \emph{等势}，记作 $A\approx B$\\
当两集合等势时，称两集合\emph{基数相等}
\begin{enum}
    \item 自反：$A\approx A$
    \item 对称：若 $A\approx B$ 则 $B\approx A$
    \item 传递：若 $A\approx B\land B\approx C$ 则 $A\approx C$
    \item 综上，等势关系是等价关系，可以将所有集合划分为等价块
\end{enum}

关于集合基数比较的其它定义定理
\begin{enum}
    \item 若存在单射函数 $f:A\to B$ 则称 $|A|\le |B|$
    \item 若 $\big(|A|\le |B|\big)\land \big(|A|\ge |B|\big)$ 则 $|A|=|B|$
\end{enum}

定义标准集合的基数：
\begin{enum}
    \item 空集：$|\varnothing|=0$
    \item $n\in \mathbb N$，$N_n = \{1,2,\cdots,n\}$，定义 $|N_n|=n$
    \item $|\mathbb N| = \aleph_0$
    \item $|\mathbb R| = \aleph$
\end{enum}

若 $A\approx \varnothing$ 或 $A\approx N_n$ 则 $A$ 是\emph{有穷集}，否则 $A$ 是\emph{无穷集}\\
若 $A\approx \mathbb N$ 则$A$ 是\emph{可数集}或\emph{可列集}

\subsubsection{可数集}
\begin{enum}
    \item 若 $A$ 是无穷集，则：$A$ 是可数集$\iff A$ 可写为 $A=\{a_1,a_2,\cdots\}$ 
    \item 若 $A$ 为可数集且$a\in A$，则 $A\approx (A\backslash \{a\})$\\
          任何可数集中取出\textbf{有穷个}元素后仍是可数集；任何可数集与它的无穷真子集等势
    \item $A$ 是无穷集 $\iff A$ 有一子集为可数集 $\iff A$ 与其一真子集等势
    \item 可数集的无穷子集是可数集
    \item 有穷个可数集的并集为可数集
    \item 有穷个可数集的叉积为可数集
\end{enum}

\paragraph{第一象限的整数点集为可数集}
按照图 \ref{fig:平面上第一象限点是可数集} 中的方式就可以将第一象限整数点进行排序\\
设第一象限整数点 $(m,n)$ 排行第 $k$，则：
$$
k = f(m,n) = 1 + 2 + \cdots + (m+n) + (m+1) = \frac{1}{2} \big[(m+n)^2+3m+n] + 1
$$
因此第一象限的整数点集是可数集

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.4\textwidth]{figures/平面上第一象限点是可数集.png}
    \caption{平面上第一象限点是可数集}
    \label{fig:平面上第一象限点是可数集}
\end{figure}

\paragraph{正有理数集是可数集}
正有理数集 $\mathbb Q^+$ 显然与平面上第一象限整数点集的一个无穷真子集等势\\
因此，正有理数集是可数集

\subsubsection{不可数集合}
\begin{enum}
    \item $(0,1)$ 区间上的实数$\mathbb R_{(0,1)}$集合不是可数集
    \item $\mathbb R_{(0,1)} \approx \mathbb R$，$|\mathbb R_{(0,1)}| = |\mathbb R| = \aleph$
    \item $\mathbb R_{(0,1)} \approx \mathbb R_{(0,1)} \times \mathbb R_{(0,1)}$
    \item $\aleph > \aleph_0$
\end{enum}

\paragraph{平面实数点集的基数}
对实数开区间 $(0,1)$，有 $(0,1) \approx (0,1) \times (0,1)$

假定 $(a,b) \in (0,1) \times (0,1)$ 则可令：
\begin{align*}
    a &= 0.a_1a_2a_3\cdots \\
    b &= 0.b_1b_2b_3\cdots
\end{align*}
则可以构造 $x = 0.a_1b_1a_2b_2a_3b_3\cdots \in (0,1)$\\
这种构造方法是一个双射函数，因此 $(0,1) \approx (0,1)\times (0,1)$

\begin{quote}
    进一步，正方形区域 $(0,1)\times(0,1)$ 可双射到平面区域 $\mathbb R\times\mathbb R$\\
    还可进一步推证：解析几何空间点集的基数为 $\aleph$
\end{quote}


\subsubsection{不存在最大基数集合}

设 $A$ 为一集合，则 $|A|\ne |2^A|$\\
又可构造单射函数证明 $|A| < |2^A|$\\
因此$|2^A| > |A|$，不存在最大基数的集合

\section{图论}
\subsection{图的基本概念}
定义一：\emph{图} $G=(V,E)$ 是一个系统，其中：
\begin{enum}
    \item $V$ 是一个非空有限集合，$V$ 中每个元素 $v\in V$ 都称为图 $G$ 的一个\emph{结点}
    \item $E$ 是一个有限集合，$E$ 中元素称为\emph{边}，$E$ 中元素与 $V$ 中的一对元素相联系
\end{enum}

\begin{quote}
    定义一没有明确点、线之间的关系
\end{quote}

定义二：\emph{图} $G=(V,E)$ 是一个系统，其中：
\begin{enum}
    \item $V$ 是一个非空有限集合，$V$ 中每个元素 $v\in V$ 都称为图 $G$ 的一个\emph{结点}
    \item $E\subseteq V\times V$，$E$ 中元素称为\emph{边}
\end{enum}

\begin{quote}
    定义二清晰地描述了点线关系，虽无法描述平行边，但对很多情况足够使用，对简单图常用
\end{quote}

定义三：\emph{图} $G=(V,\Sigma,E)$ 是一个系统，其中：
\begin{enum}
    \item $V$ 是一个非空有限集合，$V$ 中每个元素 $v\in V$ 都称为图 $G$ 的一个\emph{结点}
    \item $\Sigma$ 是一个标号集合，$E\in V\times \Sigma\times V$，称$G=(V,\Sigma,E)$ 为一个图
    \item $u,v\in V$，$\sigma\in \Sigma$，若 $(u,\sigma,v)\in E$ 则称 $(u,\sigma,v)$ 为 $G$ 中的一条\emph{边}
\end{enum}

\begin{quote}
    定义三能够严格定义点线关系并描述多重边，但比较复杂，研究简单图时一般不采用
\end{quote}

定义四：\emph{图} $G=(V,\Sigma,E)$ 是一个系统，其中：
\begin{enum}
    \item $V$ 是一个非空有限集合，$V$ 中每个元素 $v\in V$ 都称为图 $G$ 的一个\emph{结点}
    \item $E$ 是一个有限集合，$E$ 中每个元素 $e\in E$ 都称为图 $G$ 的一条\emph{边}
    \item $\gamma$ 是边到结点集的一个关联函数，即$\gamma:E\to 2^V$
\end{enum}

\begin{quote}
    定义四不再将边视为点的附属，但关联函数比较繁琐，简单图一般不采用
\end{quote}

对于图 $G=(V,E)$，$u,v\in V$
\begin{enum}
    \item 无向边：$(u,v)$ 与 $(v,u)$ 表示同一条边
    \item 有向边：$(u,v)$ 与 $(v,u)$ 表示不同的边
    \item 无向图：所有边均为无向边
    \item 有向图：所有边均为有向边
    \item 混合图：既有有向边又有无向边
    \item 零图：没有一条边，即 $E=\varnothing$
    \item 平凡图：仅有一个结点 $|V|=1$，即 $|V|=1$
\end{enum}

关于点和边的定义
\begin{enum}
    \item 二边邻接：有公共端点的两条边
    \item 二结点相邻：同一条边的两个端点
    \item 孤立点：不与任何边关联的结点
    \item 平行边：有相同的起点和终点的两条边
    \item 重数：两结点间平行边的条数
    \item \emph{多重图}：具有平行边的图，其重数定义为所有重数的最大值
    \item \emph{简单图}：无平行边且无自环的图
\end{enum}

\subsubsection{子图与补图}
$G=(V,E)$ 为简单图，$G$ 中的每一对不同的结点间都有边相邻，则称$G$ 为\emph{完全图}
\begin{enum}
    \item $n$ 个结点$m$条边的无向完全图：$m=n(n-1)/2$
    \item $n$ 个结点$m$条边的有向完全图：$m=n(n-1)$
    \item $n$ 结点的无向完全图记为 $\boldsymbol k_n$
\end{enum}

$G=(V,E)$ 且 $G'=(V',E')$
\begin{enum}
\item 若 $V'\subseteq V \land E'\subseteq E$ 则 $G'$ 为 $G$ 的\emph{子图}
\item 若 $V'\subset V \land E'\subset E$ 则 $G'$ 为 $G$ 的\emph{真子图}
\item 若 $V' = V \land E'\subseteq E$ 则 $G'$ 为 $G$ 的\emph{生成子图}
\item 若 $V' = V \land E' = E$ 或 $V'=V \land E'=\varnothing$则 $G'$ 为 $G$ 的\emph{平凡子图}
\end{enum}

$G=(V,E)$ 是简单图，$G^*=(V,E^*)$ 是与 $G$ 对应的完全图，$\bar G = (V,\bar E)$ 为$G$ 的\emph{补图}，其中 $\bar E = E^*\backslash E$

$G=(V,E)$ 是图
\begin{enum}
\item $G$ 为有向图，$G$ 中以结点 $v$ 为起点的边的条数为结点 $v$ 的\emph{出度} $\overleftarrow{\rm deg}(v)$
\item $G$ 为有向图，$G$ 中以结点 $v$ 为终点的边的条数为结点 $v$ 的\emph{入度} $\overrightarrow{\rm deg}(v)$
\item $G$ 为无向图，$G$ 中以结点 $v$ 为端点的边的条数为结点 $v$ 的\emph{度} ${\rm deg}(v)$
\item 度为奇数的结点为\emph{奇节点}，度为偶数的结点为\emph{偶节点}，
\item 度为1的结点称为\emph{悬挂点}，与之关联的边称为\emph{悬挂边}
\end{enum}

与度相关的定理：$G=(V,E)$ 有 $n$ 个结点 $m$ 条边
\begin{enum}
\item 若 $G$ 是无向图，则 $\sum_{i=1}^n\operatorname{deg}(v_i)=2m$
\item 若 $G$ 是无向图，则奇结点有偶数个
\item 若 $G$ 是有向图，则 $\sum_{i=1}^n\overleftarrow{\rm deg}(v_i) = \sum_{i=1}^n\overrightarrow{\rm deg}(v_i)=m$
\end{enum}

\subsubsection{图的重构}
$G=(V,E)$ 与 $G'=(V',E')$ 是两个\textbf{简单无向图}\\
若存在从 $V$ 到 $V'$ 的双射函数 $h$ 使 $e=\{v_i,v_j\}\in E \iff e'=\{h(v_i),h(v_j)\}\in E'$ 则称 $G$ 与 $G'$ \emph{同构}

$G=(V,E)$ 与 $G'=(V',E')$ 是两个\textbf{简单有向图}\\
若存在从 $V$ 到 $V'$ 的双射函数 $h$ 使 $e=(v_i,v_j)\in E \iff e'=\big(h(v_i),h(v_j)\big)\in E'$ 则称 $G$ 与 $G'$ \emph{同构}

\subsection{路与圈}
设 $G=(V,E)$ 为图，$W$ 是$G$ 的有限非空点边交错序列 $w=v_0e_1v_1e_2\cdots e_kv_k$\\
称 $W$ 为$G$ 的一条从 $v_0$ 到 $v_k$ 的\emph{途径}，称 $v_0$ 为途径的起点，$v_k$ 为途径的终点，$k$ 为途径的\emph{长度}
\begin{enum}
\item 若 $v_0\ne v_k$ 则称 $W$ 是从 $v_0$ 到 $v_k$ 的一条\emph{路}
\item 若 $v_0= v_k$ 则称 $W$ 是\emph{圈}
\item 无重复边，称\emph{简单路}/\emph{简单圈}
\item 无重复点，称\emph{初级路}/\emph{初级圈}
\item 初级路（圈）一定是简单路（圈）
\end{enum}

$G = (V,E)$ 为简单图，若 $|V|=n$ 则
\begin{enum}
    \item 初级路的长度不超过 $n-1$
    \item 初级圈的长度不超过 $n$
\end{enum}

\subsubsection{可达性}
$G=(V,E)$ 是图，$\forall u,v\in V$，若 $G$ 中存在从 $u$ 到 $v$ 的路，则称 $u$ \emph{可达} $v$
\begin{enum}
    \item 无向图中： $u$ 可达$v \iff v$ 可达 $u \iff u$ 与 $v$ 相互可达
    \item 有向图中： $u$ 与 $v$ 相互可达 $\iff u$ 可达 $v$且 $v$ 可达 $u$
    \item 从 $u$ 到 $v$ 长度最短的路称为\emph{短程线}
    \item 从 $u$ 到 $v$ 短程线的长度称为从 $u$ 到 $v$ 的\emph{距离}，记为 $\operatorname{d}(u,v)$
    \item 规定：若 $u$ 不可达 $v$ 则 $\operatorname{d}(u,v)=\infty$
    \item 规定：$u$ 总是可达 $u$，且 $\operatorname{d}(u,u)=0$
\end{enum}

\begin{quote}
    对于无向图，可达性是自反、对称、传递的\\
    在结点集合 $V$ 上确定了一个划分，也在边集 $E$ 上确定了一个划分
\end{quote}

对于无向图 $G=(V,E)$
\begin{enum}
\item $G$ 的极大连通子图称为 $G$ 的一个\emph{连通分支}\\
      $G$ 的每个结点和边都处于且仅处于一个连通分支中
\item 若 $G$ 中的任意两个结点均可达，则称 $G$ \emph{连通}，否则称 $G$ \emph{非连通}\\
      无向图 $G$ 是连通的 $\iff$ $G$ 有且仅有一个连通分支
\end{enum}

对于有向图 $G=(V,E)$
\begin{enum}
\item 若任意两结点之间都是相互可达，则称 $G$ 是\emph{强连通}的
\item 若任意两结点之间至少单向可达，则称 $G$ 是\emph{单向连通}的
\item 若略去边的方向后任意两结点之间互相可达，则称 $G$ 是\emph{弱连通}的
\item 称 $G$ 的极大强连通子图为 $G$ 的\emph{强连通支}
\item 称 $G$ 的极大单项连通子图为 $G$ 的\emph{单向连通支}
\item 称 $G$ 的极大弱连通子图为 $G$ 的\emph{弱连通支}
\item 每个结点都恰好处于一个强连通支中
\item 每个结点、每个边都恰好处于一个弱连通支中
\item 每个结点、每条边都至少处于一个单向连通支中
\end{enum}

\begin{quote}
    对于有向图：\\
    弱连通在$V,\,E$ 上各建立了一个划分\\
    强连通只在 $V$ 上建立了划分，而不能覆盖所有的边 \\
    单向连通只能建立 $V,\,E$ 上的覆盖
\end{quote}

\subsection{图的矩阵表示}
若 $G=(V,E)$ 是\textbf{简单有向图}，称 $n$ 阶方阵 $A=(a_{ij})_{n\times n}$ 是$G$ 的邻接矩阵，其中
$$
a_{ij} = 
\begin{cases}
    1, &(v_i,v_j)\in E\\
    0, &(v_i,v_j)\not\in E\\
\end{cases}
$$

简单有向图的邻接矩阵
\begin{enum}
    \item 简单有向图的邻接矩阵完整刻画了其结点间的邻接关系
    \item 如若结点命名发生变化，则邻接矩阵中相应的行、列顺序对调
    \item 两图同构 $\iff$ 一个邻接矩阵可通过行列交换变为另一个
    \item 由于是简单图，无自环，邻接矩阵的主对角线元素全为0
    \item 邻接矩阵某行之和 = 对应结点的出度
    \item 邻接矩阵某列之和 = 对应结点的入度
    \item 邻接矩阵行列之和 = 对应结点的度
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/邻接矩阵.pdf}
    \caption{邻接矩阵}
    \label{fig:邻接矩阵}
\end{figure}

邻接矩阵的运算
\begin{enum}
\item $B=AA^{\rm T}$，则 $b_{ij} = \sum_{k=1}^na_{ik}a_{kj}^{\rm T} = \sum_{k=1}^na_{ik}a_{jk}$\\
      $b_{ij}=n$ 说明存在 $n$ 个结点，使得 $v_i$ 与$v_j$ 发出的边都终止于它 \\
      $AA^{\rm T}$ 主对角线元素的值表示结点出度
  \item $B=A^{\rm T}A$，则 $b_{ij} = \sum_{k=1}^na^{\rm T}_{ik}a_{kj} = \sum_{k=1}^na_{ki}a_{kj}$\\
      $b_{ij}=n$ 说明存在 $n$ 个结点，它发出的边既有到达 $v_i$ 的又有到达 $v_j$ 的\\
      $A^{\rm T}A$ 主对角线元素的值表示结点入度
  \item $(A^m)_{ij}$ 的值是从 $v_i$ 到 $v_j$ 长度为 $m$ 的路的数量
\end{enum}

\subsubsection{可达矩阵}
$G=(V,E)$ 为$(n,m)$ \textbf{简单有向图}，定义$n$ 阶方针 $R=(r_{ij})_{n\times n}$ 为图 $G$ 的\emph{可达矩阵}
\begin{align*}
    r_{ij} &= 
    \begin{cases}
        1, & v_i \text{\,可达\,} v_j\\
        0, & v_i \text{\,不可达\,} v_j\\
    \end{cases} & 
    r_{ii} &= 
    \begin{cases}
        1, & v_i \text{\,有圈到\,} v_i\\
        0, & v_i \text{\,无圈到\,} v_i\\
    \end{cases}
\end{align*}

\paragraph{可达矩阵的直接求法}

在 $(n,m)$ 图中
\begin{enum}
    \item 若从 $v_i$ 到 $v_j$ 有路，则必有初级路，其长度不超过 $n-1$
    \item 若从 $v_i$ 到 $v_i$ 有圈，则必有初级圈，其长度不超过 $n$
\end{enum}

因此，可用如下方式计算可达矩阵（$A^{(i)}$ 为矩阵乘法幂，但加、乘均为布尔加、布尔乘）
$$
R = A + A^{(2)} + A^{(3)} + \cdots + A^{(n)}
$$


\paragraph{可达矩阵的Warshall算法}
计算矩阵序列 $R^{(0)},R^{(1)},\cdots,R^{(n)}$ 
\begin{enum}
\item $R^{(0)}=A$
\item 在$2\le k\le n$ 时，有如下递推关系：$r_{ij}^{(k)} = r_{ij}^{(k-1)} \lor \left(r_{ik}^{(k-1)} \land r_{kj}^{(k-1)}\right)$
\item $R = R^{(n)}$
\end{enum}

\begin{quote}
    $r_{ij}^{(k)} = 1 \iff $ 结点 $i,j$ 之间直接相连或通过结点 $1,2,\cdots,k$ 相连
\end{quote}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/可达矩阵计算.pdf}
    \caption{可达矩阵的Warshall算法}
    \label{fig:可达矩阵计算}
\end{figure}

\paragraph{可达矩阵与有向图的连通性}
\vspace{1em}
\begin{enum}
    \item \makebox[3.1cm][l]{有向图 $G$ 强连通  } $\iff$ 可达矩阵 $R$ 全1
    \item \makebox[3.1cm][l]{有向图 $G$ 单向连通} $\iff$ $R\lor R^{\rm T}$ 除主对角线外全1
    \item \makebox[3.1cm][l]{有向图 $G$ 弱连通  } $\iff$ 由矩阵 $A\lor A^{\rm T}$ 确定的可达矩阵$R$ 全1
    \item \makebox[3.1cm][l]{有向图 $G$ 中有圈  } $\iff$ 可达矩阵 $R$ 的某些主对角线元素 $r_{ii}=1$
\end{enum}

\begin{quote}
    注意，所有关于可达矩阵的讨论都是针对有向图
\end{quote}

\subsection{带权图的最短路径}
$G=(V,E)$ 是简单图，$\forall e\in E$，存在一正实数 $W(e)$ 与之对应，称  $W$ 是 $G$ 的\emph{权函数}，称 $G$ 为\emph{带权图}

设$\mu = (e_{i1},e_{i2},\cdots,e_{ik})$ 是带权图中的一条路，则其\emph{路长}为 $W(\mu) = \sum\limits_{l=1}^kW(e_{il})$

\subsubsection{带权图的最短路算法}

Dijkstra算法
\begin{enum}
    \item 起点为 $v_0$，终点为 $v$
    \item 将结点分为两组：有P标号的结点、有T标号的结点
    \item 对有P标号的结点$a$，其标号值表示从 $v_0$ 到 $a$ 的最短路长
    \item 对有T标号的结点$b$，其标号值表示从 $v_0$ 到 $b$ 的某条路径长度
\end{enum}

Dijkstra算法的步骤
\begin{enum}
    \item 将$v_0$ 取为值为0的P标号，其余结点为T标号\\
        若由 $v_0$ 通过某边可达结点 $a$，则$a$ 的T标号值$\operatorname{d}(a)$为此边的权$W(v_0,v_1)$，否则$a$ 的T标号值为 $\infty$
    \item 将最小T标号的结点$v_1$置为P标号，$v_1$的标号值不变\\
        与$v_1$相邻的所有结点 $a$ 更新 $T$标号为 $\operatorname{d}(a) = \min\big\{\operatorname{d}(a),\operatorname{d}(v_1)+W(v_1,a)\big\}$
    \item 重复上述过程，直至终点 $v$ 称为 P标号
\end{enum}

\subsection{Euler图}
设 $G=(V,E)$ 为\textbf{无向连通图}
\begin{enum}
\item 若某条路通过 $G$ 中每条边一次且仅一次，则此路为 \emph{Euler路}
\item 若某个圈通过 $G$ 中每条边一次且仅以此，则此圈为 \emph{Euler圈}
\item 若$G$中由Euler圈，则$G$为 \emph{Euler图}
\end{enum}

\emph{Euler定理}：
\begin{enum}
    \item 无向连通图$G$是Euler图 $\iff G$ 中的每个结点都是偶节点 
    \item 无向连通图$G$有Euler路 $\iff G$ 中有且仅有2个奇结点
    \item 有向连通图$G$是Euler图 $\iff G$ 的每个结点的出度=入度
    \item 有向连通图$G$有Euler路 $\iff G$ 的结点中仅有两个出度与入度不相等，且：\\
        其中一个结点出度比入度多一，另一个结点出度比入度少一
\end{enum}

在Euler图中寻找Euler圈：
\begin{enum}
    \item 任选一个简单圈 $C$
    \item 若 $C$ 不是Euler圈，则由Euler图的连通性知：有不属于 $C$ 的边 $e_i$ 与 $C$ 中结点 $v_i$ 相邻
    \item 总可以从 $v_i$ 沿 $e_i$ 出发，经过一个简单圈 $C_i$ 后回到 $v_i$
    \item 将简单圈$C_i$并入 $C$ 中，得到一个更大的简单圈
    \item 重复上述过程直到$C$ 为Euler圈
\end{enum}

在有Euler路的图中寻找Euler路（Fleury算法）
\begin{enum}
\item 定义：若某边断开后图的连通支增加，则此边称为\emph{割边}
\item 从一个奇结点出发，每走一边就抹去此边
\item 在此过程中，仅在没有其它选择时才走割边
\end{enum}

\subsection{Hamilton图}
Hamilton路、圈、图：
设$G=(V,E)$是简单图
\begin{enum}
\item \emph{H-路}是一条初级路，它穿过图中每个结点一次且仅一次；
\item \emph{H-圈}是一条初级圈，它穿过图中每个结点一次且仅一次；
\item \emph{H-图}是含有H-圈的图
\end{enum}

判断Hamilton图的\textbf{必要条件}\\
若$G=(V,E)$是简单无向图，则：$G$是Hamilton图 $\;\Longrightarrow\;\big(\forall S\subseteq V\big)\big(S\ne \varnothing\;\Longrightarrow\; W(G\backslash S)\le |S|\big)$\\
其中 $W(G\backslash S)$ 表示 $G\backslash S$ 的连通支数

\begin{quote}
    从Hamilton图 $G$ 中删去 $|S|$ 个结点后，$G\backslash S$ 的连通支数不大于删去的结点数 $|S|$
\end{quote}

判断Hamilton图的\textbf{充分条件}
\begin{enum}
    \item 设 $G=(V,E)$ 是有 $n$ 个结点的简单无向图，若 $\forall u,v\in V$ 有$\operatorname{deg}(u)+\operatorname{deg}(v)\ge n-1$\\
        则 $G$ 中必有一条 H-路
    \item 设 $G=(V,E)$ 是有 $n$ 个结点的简单无向图，若 $\forall u,v\in V$ 有$\operatorname{deg}(u)+\operatorname{deg}(v)\ge n$\\
        则 $G$ 中必有一个 H-圈，$G$是Hamilton图
\end{enum}

判断Hamilton图的\textbf{必要条件}
\begin{enum}
    \item 任取一结点用 A 标记，所有与之相邻的结点用 B 标记
    \item 再用 A 标记邻接余 B的结点，再用B标记邻接于A的结点……
    \item 若发现有两相同标号结点相邻，则在连接此两点的边上增加一异号结点
    \item 如果图中有一条H-圈，那么它必交替通过结点A和B\\
          因此：标记A的结点与标记B的结点数目或者相同，或者相差1个
\end{enum}

\subsubsection{竞赛图}
完全图的定向图称为\emph{竞赛图}

设 $G=(V,E)$ 是竞赛图，且 $|V|=n$，则 $G$ 中必有一条 H-路

\subsubsection{旅行商问题}
在带权图$G=(V,E,w)$中寻求最优H-圈问题，有如下\textbf{近似算法}：

\paragraph{近邻法}
\vspace{1em}
\begin{enum}
    \item 在 $G$ 中任选结点 $v_1$，从 $v_1$ 出发，寻找距$v_1$最近的一个结点 $v_2$，得到初级路 $C=(v_1,v_2)$，$i=1$
    \item 从 $v_i$ 出发，在$V\backslash C$ 中寻找距$v_i$ 最近的结点$v_{i+1}$，将$C$ 延伸至$v_{i+1}$，$i=i+1$
    \item 重复上一步，直到 $i=n$
    \item $i=n$ 时将 $C$ 从 $v_{n}$ 延伸至 $v_1$ 得到一个 H-圈
\end{enum}

\paragraph{交换法}
\vspace{1em}
\begin{enum}
    \item 在图 $G$ 中任选一个 H-圈$C=(v_1,v_2,\cdots,v_n,v_1)$
    \item 对于 $i=j$ 若能找到$w(v_i,v_j)+w(v_{i+1},v_{j+1}) < w(v_i,v_{i+1})+w(v_{j},v_{j+1})$\\
        则令 $C=(v_1,\cdots,v_{i},v_{j},v_{j-1},\cdots,v_{i+1},v_{j+1},v_{i+2},\cdots,v_n,v_1)$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/旅行商问题的交换法.png}
    \caption{旅行商问题的交换法}
    \label{fig:旅行商问题的交换法}
\end{figure}


\subsection{二分图}
$G=(V,E)$ 为简单无向图，若存在 $V$ 的一个划分 $V=V_1\cup V_2$ \\
使得$G$ 中的每条边的一个端点在 $V_1$ 中，另一端点在 $V_2$ 中\\
则称$G$ 为\emph{二分图}，称 $V_1,V_2$ 为 $V$的\emph{互补结点子集}\\
当 $V_1$ 中的每个结点都与 $V_2$ 中的每个结点相邻，则称\emph{完全二分图}

\subsubsection{二分图的判定}
判断二分图的充要条件\\
设 $G=(V,E)$ 是简单无向图，则：$G$ 为二分图$\iff$ $G$ 中每个圈的长度都是偶数

推论：判断简单无向图 $G=(V,E)$ 为二分图的步骤
\begin{enum}
    \item 在 $G$ 中任取一结点$w_0$，给以标号A
    \item 若$G$ 中还有未标号的结点，凡是与A标号结点相邻的标号结点都标以B标号\\
          若产生两个相邻的B标号结点，则$G$不是二分图，EXIT
    \item 若$G$ 中还有未标号的结点，凡是与B标号结点相邻的标号结点都标以A标号\\
          若产生两个相邻的A标号结点，则$G$不是二分图，EXIT
    \item 重复上两步，直到所有结点都有标号
    \item 若 $|V|=1$ 则$G$ 不是二分图\\
          若$|V|\ge 2$ 则$G$ 是二分图，且具有 $A$ 标号的结点构成 $V_1$，具有 $B$ 标号的结点构成 $V_2$
\end{enum}

\subsubsection{匹配问题}
设 $G=(V,E)$ 是二分图，$E\subseteq V_1\times V_2$
\begin{enum}
\item 若 $M\subset E$，且 $M$ 中任何两条边都不相邻，则 $M$ 是$G$ 的一个\emph{匹配}
\item 具有边数最多的匹配称为\emph{最大匹配}
\item 若 $|V_1|=|V_2|=|M|$ 则称 $M$ 为\emph{完美匹配}
\item 匹配$M$中的边$e\in M$称为\emph{杆}
\end{enum}

完美匹配的存在性判定：
\begin{enum}
\item 若 $|V_1|\ne |V_2|$ 则不存在完美匹配
\item 若 $|V_1| = |V_2|$ 且所有节点的度相同，则存在完美匹配
\end{enum}

设 $M$ 是一匹配
\begin{enum}
\item \makebox[5cm][l]{结点  $u\in V_1, v\in V_2$ 被$M$匹配       } $\iff$ 有杆$e=(u,v)\in M$ 
\item \makebox[5cm][l]{$u\in V_1\cup V_2$ 为 $M$ 的\emph{饱和点}  } $\iff$ 有杆 $e\in M$ 匹配结点 $u$
\item \makebox[5cm][l]{$u\in V_1\cup V_2$ 为 $M$ 的\emph{非饱和点}} $\iff$ 无杆 $e\in M$ 匹配结点 $u$
\item \emph{交错路} $P$ 指一条分别交替属于 $M$ 和 $E\backslash M$ 的边构成的极大初级路/初级圈
\item \emph{增广路} $P$ 是一条起点、终点都是非饱和点的交错路
\end{enum}

求最大匹配的匈牙利算法
\begin{enum}
    \item 任取一匹配 $M$，令 $V_1$ 中$M$ 的非饱和点构成集合 $S$
    \item 若 $S=\varnothing$ 则 $M$ 就是所求最大匹配，EXIT
    \item 任取非饱和点 $u_0\in S$作为起点\\
          若能走出增广路$P$，则令 $M=M\oplus P$，更新 $S$\\
          若走不出增广路$P$，则令 $S=S\backslash{u_0}$\\
          回到第二步
\end{enum}

\subsection{平面图}
若无向图 $G=(V,E)$ 存在一种图示使得任意两条边不相交，则称$G$ 为\emph{平面图}

判定平面图的必要条件：在$(n,m)$\textbf{连通平面图}$G$的图示中
\begin{enum}
    \item 一个极小的初级圈所包围的部分称为平面图的一个区域，此初级圈的边为此区域的边界
    \item 平面图最大的初级圈之外的部分为平面图的无穷域，最大初级圈的边称为无穷域的边界
    \item 若$G$ 有 $n$ 个结点，$m$ 条边，$r$ 个区域，则 $n-m+r=2$
    \item 若每个区域由三条或更多边围成，则 $m\le 3n-6$
    \item 若每个区域由四条或更多边围成，则 $m\le 2n-4$
\end{enum}

\subsubsection{Kuratowski定理}
图$G=(V,E)$是平面图的充要条件：\\
$G$中无一子图或无一经过Kuratowski技术之后的子图与$K_5$ 或 $K_{3,3}$同构。
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/K5K6K33.pdf}
    \caption{$K_5, K_6, K_{3,3}$}
    \label{fig:K5-K6-K33}
\end{figure}

定理中的Kuratowski技术是指：
\begin{enum}
    \item 当两点间已有边时，在两点间增加重复边或删去重复边
    \item 当两点间已有边时，在边上增加一个结点，使一条边变成两条边
    \item 当两个结点都与第三个结点邻接，而第三个结点的度数为2时，删去第三个结点而使两边合为一边
\end{enum}

\subsection{树}
\subsubsection{自由树}
$G=(V,E)$ 是一个无向图，若 $G$ \textbf{连通且无圈}，则称 $G$ 是\emph{自由树}，树的边称为\emph{树枝}\\
若结点 $v$ 的度是1，则$v$ 称为\emph{叶子}，否则$v$称为\emph{分支点}

若 $G=(V,E)$ 是$(n,m)$ 无向图，则下边六种说法等价
\begin{enum}
    \item $G$ 是树
    \item $G$ 的每一对结点间有且只有一条路
    \item $G$ 是连通的且 $m=n-1$
    \item $G$ 是无圈的且 $m=n-1$
    \item $G$ 是连通的，但若在 $G$ 的所有的边中删除一条边，则恰成为两个连通支
    \item $G$ 是无圈的，但若在 $G$ 的任意一对结点间加一边，则恰形成一个圈
\end{enum}

$G=(V,E)$ 是一个无向图，若 $G$ \textbf{无圈}，则称 $G$ 是\emph{森林}

\subsubsection{生成树}
设 $G=(V,E)$是一个无向图，$T=(V,\widetilde{E})$ 是 $G$ 的一个生成子图\\
若 $T$ 是树，则称 $T$ 为 $G$ 的\emph{生成树}

若 $G=(V,E)$是一个无向图，则：$G$ 有生成树 $\iff G$ 为连通图\\
若 $G=(V,E)$是一个连通图，则：$G$ 的生成子图 $T=(V,\widetilde{E})$ 是生成树 $\iff T$ 连通且 $\big|\widetilde{E}\big|=n-1$\\

\paragraph{寻找生成树之破圈法}
在无向连通图 $G$ 中寻找生成树：
\begin{enum}
    \item 若 $G$ 中无圈，则$G$ 即为 $G$ 的生成树，EXIT
    \item 在 $G$ 中寻找圈 $C$，在 $C$ 中任意删除一边，令 $G\coloneqq G\backslash\{e\}$，回到第一步
\end{enum}

\paragraph{寻找生成树之避圈法}
设无向连通图 $G$ 的边集为 $E=(e_1,e_2,\cdots,e_m)$，则可通过如下过程构造生成树
\begin{enum}
\item 任取一边 $e$，令 $T\coloneqq\{e\}$，$i\coloneqq 1$
\item 任取一边 $e$，若 $T\cup \{e\}$ 无圈，则 $T\coloneqq T\cup \{e\}$，$i\coloneqq i+1$
\item 若$i=n-1$ 则 EXIT，否则重复第二步
\end{enum}

\subsubsection{最小生成树}
设 $G=(V,E,W)$ 是带权图，若 $T=\{e_1,e_2,\cdots,e_{n-1}\}$ 是 $G$ 的生成树，定义 $W(T) = \sum_{i=1}^{n-1}W(e_i)$\\
有最小的 $W(T)$ 的生成树 $T_0$ 称为 $G$ 的最小生成树

\paragraph{寻找最小生成树之Kruskal算法}
如图 

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.4\textwidth]{figures/Kruskal算法.png}
    \caption{Kruskal算法流程图}
    \label{fig:Kruskal算法流程图}
\end{figure}

\paragraph{寻找最小生成树之破圈法}
\vspace{1em}
\begin{enum}
    \item $T \coloneqq G$
    \item 若 $T$ 中无圈，则 $T$ 就是所寻最小生成树
    \item 在 $T$ 中找到一个圈 $C$，寻找 $C$ 中权值最大的边 $e$，令 $T\coloneqq T\backslash\{e\}$，回到第二步
\end{enum}

\subsubsection{有根树}
$G=(V,E)$ 是有向图，满足以下条件时，称 $G$ 为\emph{有根树}
\begin{enum}
    \item 有一结点$r$ 的入度为 $0$，称为 $G$ 的\emph{根}
    \item 其他节点$v\ne r$ 入度均为1
    \item $r$ 可达其它任何结点
\end{enum}

$T = (V,E)$ 是一个有根树，$r$是$T$ 的根，则对于 $T$ 中任意结点$v$ 均存在唯一的有向路使得 $r$ 可达 $v$

设 $T = (V,E)$ 是有根树
\begin{enum}
\item 若 $\big(\forall v\in V\big)\big(\overleftarrow{\rm deg}(v)\le m\big)$ 则称此有根树为 \emph{m叉树}
\item 若 $\big(\forall v\in V\big)\big(\overleftarrow{\rm deg}(v) =  m \lor \overleftarrow{\rm deg}(v) = 0\big)$ 
      则称此有根树为\emph{完全m叉树}
\end{enum}





